#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <math.h>
using namespace std;
/*
解决区间调度问题的动态规划算法
*/
void dp_for_is(int A[9][2], int val[], int n){
    int dp[n+1];
    dp[0] = 0;
    dp[1] = val[0];
    for (int i = 2; i <= n; i++) {
        //对于活动A[i]，要么选择，要么不选择
        //不选择的最大收益dp[i-1]
        //如果选择,寻找A[0, i-2]中结束时间最大，但是小于A[i-1]的时间的序号k，则最大收益为A[i-1] + dp[k+1]
        //如果找不到？？？
        //找不到:
        int max = 0;
        int k = -1;
        for (int j = 0; j <= i-2; j++) {
            if (A[j][1] > max && A[j][1] < A[i-1][0]) {
                max = A[j][1];
                k = j;
            }
        }
        if (k == -1) {
            //如果没有找到
            dp[i] = fmax(val[i-1], dp[i-1]);
        } else {
            dp[i] = fmax(val[i-1] + dp[k+1], dp[i-1]);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dp[i] << endl;
    }
}
int main(){
    int activities[9][2] = {
        {0,2},
        {0,5},
        {4,8},
        {7,9},
        {11,13},
        {0,14},
        {12,15},
        {18,19},
        {17,20}
    };
    //已经将活动按照结束的时间升序排序
    int val[9] = {2, 5, 4, 2, 2, 14, 3, 1, 3};
    dp_for_is(activities, val, 9);
    return 0;
}